package main

import "fmt"

/*
二分查找的思路：假设查找的数是findVal
1、arr是一个有序数组，并且是从小到大排序
2、先找到中间的下标middle=(leftIndex+rightIndex)/2，然后让中间下标的值和findVal进行比较
3、如果arr[middle]>findVal，就应该向leftIndex ~ (middle-1)
4、如果arr[middle]<findVal，就应该向middle+1 ~ rightIndex
5、如果arr[middle]==findVal，就找到
6、上面的3,4,5的逻辑会递归执行

7、什么情况下，就说明找不到，分析出退出递归的条件
if leftIndex > rightIndex{
	//找不到
	return ...
}
*/
func BinaryFind(arr *[6]int, leftIndex int, rightIndex int, findVal int) {
	//判断leftIndex是否大于rightIndex
	if leftIndex > rightIndex {
		fmt.Println("找不到")
		return
	}
	//先找到中间的下标
	middle := (leftIndex + rightIndex) / 2
	if (*arr)[middle] > findVal {
		//说明要查找的数，应该在 leftIndex ~ middle-1
		BinaryFind(arr, leftIndex, middle-1, findVal)
	} else if (*arr)[middle] < findVal {
		//说明要查找的数，应该在 middle+1 ~ rightIndex
		BinaryFind(arr, middle+1, rightIndex, findVal)
	} else {
		//找到了
		fmt.Printf("找到了，下标为%v\n", middle)
	}
}
func main() {
	arr := [6]int{1, 8, 10, 89, 1000, 1234}
	BinaryFind(&arr, 0, len(arr)-1, 2)
}
